A wide variety of information may be represented in a hierarchical structure. One example format for representing information in a hierarchical structure is the extensible markup language (XML) format. An XML document may include an arrangement of nodes containing information and may specify parent-child relationships among the nodes.
Hierarchically structured information may be encrypted to prevent exposing the information to unauthorized parties. For example, an XML document may be encrypted using an encryption key. The information contained in an encrypted XML document may be accessed using an appropriate decryption key.
It may be desirable under a variety of circumstances to apply incremental updates to hierarchically structured information. For example, a computing system may include a variety of processing devices that each generate incremental updates to an XML document. An incremental update may be applied to an encrypted XML document by decrypting all or portions of the XML document, applying the incremental update, and then re-encrypting the XML document.
A processing device that generates an incremental update to hierarchically structured information may be viewed as a trusted device in terms of access to the information. On the other hand, a processing device that applies an incremental update to hierarchically structured information may be viewed as an un-trusted device in terms of access to the information. For example, an XML document may be stored on a network-based information storage facility. As a consequence, an incremental update applied by a data storage facility may expose the unencrypted information in the XML document to unauthorized parties.